Topic 9: Sets, Relations & Functions
Welcome to this foundational section which delves into core concepts that form the very language and structural framework for much of modern mathematics and related disciplines: Sets, Relations, and Functions. We begin with Sets, which are the most basic building blocks in this structure. A set is understood as a well-defined collection of distinct objects. These objects are referred to as the elements or members of the set. The requirement of being "well-defined" is crucial, ensuring that it is unambiguously clear whether any given object belongs to the collection or not. Understanding sets is the initial step towards building more complex mathematical structures.
Our exploration of Sets involves various facets. We learn about different methods for representing sets, primarily focusing on the roster form (listing the elements) and the set-builder form (describing the properties elements must satisfy). We also classify sets based on their properties, introducing important types of sets such as the empty set (containing no elements), finite sets (with a countable number of elements), infinite sets (with infinitely many elements), and singleton sets (containing exactly one element). The concepts of subsets (where all elements of one set are in another) and proper subsets are also key, as are the ideas of a universal set (the encompassing set for a given context) and the power set (the set of all subsets). Fundamental operations on sets are studied, allowing us to combine or compare sets: union (combining elements from both sets), intersection (finding common elements), difference (finding elements in one set but not the other), and complement (finding elements outside a set within the universal set). To visualize these relationships and operations, Venn diagrams are introduced as powerful graphical tools.
Building upon the foundation of sets, we introduce the concept of Relations. A relation defines a connection or correspondence between elements of two or more sets, or sometimes between elements within the same set. Our focus is primarily on binary relations, which establish a link between elements of two sets. A significant part of studying relations involves understanding their various properties. We examine properties such as reflexive (where every element is related to itself), symmetric (where if element 'a' is related to element 'b', then 'b' must also be related to 'a'), and transitive (where if 'a' is related to 'b' and 'b' is related to 'c', then 'a' is related to 'c'). Relations that simultaneously possess all three of these properties – reflexive, symmetric, and transitive – are particularly important and are known as equivalence relations. Equivalence relations have the unique characteristic of partitioning a set into disjoint subsets called equivalence classes.
Moving forward, we arrive at Functions, which represent a special and critically important type of relation. The defining characteristic of a function is that each element in the first set (which is called the domain of the function) is associated with exactly one element in the second set (known as the codomain). Functions provide a rule or mapping that assigns a unique output for each input. Understanding the key components of a function – its domain (the set of all possible input values), its codomain (the set where the output values are expected to lie), and its range (the actual set of output values produced by the function) – is fundamental. The range is always a subset of the codomain.
We further classify functions based on the nature of their mapping. This includes studying different types of functions such as one-to-one (or injective) functions, where distinct input values always map to distinct output values; onto (or surjective) functions, where every element in the codomain is reached as an output for at least one input; and bijective functions, which are simultaneously both one-to-one and onto. Bijective functions establish a perfect pairing between the elements of the domain and the codomain. We also introduce the concept of composition of functions, which involves applying one function after another, and the notion of inverse functions, which conceptually 'undo' the action of the original function. It is important to note that inverse functions exist only for bijective functions.
A solid understanding of Sets, Relations, and Functions is absolutely crucial. These concepts serve as foundational pillars supporting more advanced areas of mathematics, including advanced algebra, calculus, topology, logic, and discrete mathematics. Moreover, they are indispensable in various branches of computer science, playing key roles in areas like database theory, algorithm analysis, and programming paradigms. Mastering these fundamental building blocks provides the necessary framework for tackling complex problems and understanding sophisticated structures across a wide range of academic and practical fields.
Sets: Fundamentals and Representation
A Set is a well-defined collection of distinct objects, called elements. Basic Concepts include membership ($a \in A$). Sets can be represented in two ways: Roster Form (listing elements, e.g., $\{1, 2, 3\}$) and Set-Builder Form (describing properties, e.g., $\{x | x \text{ is an even number}\}$). We introduce Standard Sets of Numbers ($\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}$) and their notations. An Ordered Pair $(a, b)$ has elements in a specific order. The Cartesian Product $A \times B$ of two sets A and B is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$.
Sets: Types and Cardinality
Sets are classified into various Types. An Empty Set ($\emptyset$ or \{\}) has no elements. A Finite Set has a countable number of elements; an Infinite Set does not. A Singleton Set has exactly one element. Equal Sets have the same elements; Equivalent Sets have the same number of elements (same cardinality). The Cardinal Number $|A|$ or $n(A)$ is the number of elements in a finite set. A Subset $A \subseteq B$ means every element of A is in B; B is a Superset of A. The Power Set $P(A)$ is the set of all subsets of A ($|P(A)| = 2^{|A|}$). A Universal Set ($U$) is a set containing all elements under consideration. Intervals are subsets of $\mathbb{R}$ represented by inequalities (e.g., $[a, b)$).
Set Relations
A Relation $R$ from set A to set B is a subset of the Cartesian product $A \times B$. It describes how elements of A relate to elements of B. We focus on Relations on a Set A (from A to A), which are subsets of $A \times A$. A relation can be represented as a set of ordered pairs, or visually using an Arrow Diagram connecting related elements. For a relation $R \subseteq A \times B$, the Domain is the set of all first elements of the ordered pairs, and the Range is the set of all second elements.
Types of Relations
Relations on a set can be classified by their properties. An Empty Relation ($R=\emptyset$) relates no elements; a Universal Relation ($R=A \times A$) relates every element to every other element. An Identity Relation ($I_A = \{(a, a) | a \in A\}$) relates each element only to itself. A relation R is Reflexive if $(a, a) \in R$ for all $a$. It's Symmetric if $(a, b) \in R$ implies $(b, a) \in R$. It's Transitive if $(a, b) \in R$ and $(b, c) \in R$ imply $(a, c) \in R$. A relation that is reflexive, symmetric, and transitive is an Equivalence Relation, partitioning the set into disjoint Equivalence Classes.
Set Operations and Venn Diagrams
Set operations combine sets to form new sets. The Union $A \cup B$ contains elements in A or B (or both). The Intersection $A \cap B$ contains elements common to both A and B. The Difference $A - B$ contains elements in A but not in B. The Complement $A'$ (or $A^c$) contains elements in the Universal Set $U$ but not in A. Venn Diagrams use overlapping circles within a rectangle (representing $U$) to visually represent sets and illustrate these operations.
Algebra of Sets and Cardinality Results
Set operations follow specific laws, forming the Algebra of Sets (e.g., Commutative, Associative, Distributive laws for Union and Intersection). De Morgan's Laws relate complementation with union and intersection: $(A \cup B)' = A' \cap B'$ and $(A \cap B)' = A' \cup B'$. We study Basic Results about Cardinality, such as $n(A \cup B) = n(A) + n(B) - n(A \cap B)$, which is part of the Inclusion-Exclusion Principle. These principles are applied to solve Practical Problems on Sets, often presented as word problems involving counts of elements in overlapping categories.
Functions: Definition, Domain, and Range
A Function is a special type of relation where each element in the first set (the Domain) is associated with exactly one element in the second set (the Codomain). The set of all actual output values is called the Range, which is a subset of the codomain. Key Features of a Function include having a unique output for every input from the domain. Functions are fundamental mathematical objects used to model relationships between quantities.
Types of Functions
Functions can be classified based on the mapping between their domain and codomain. A function $f: A \to B$ is One-to-One (Injective) if distinct elements in A map to distinct elements in B. It is Onto (Surjective) if every element in B has at least one preimage in A (i.e., Range = Codomain). A function that is both one-to-one and onto is Bijective. Functions that are not one-to-one are Many-to-One. Functions whose range is a proper subset of the codomain are called Into Functions (if not surjective).
Real Functions and Their Graphs
A Real Function is a function whose domain and codomain are subsets of the set of real numbers ($\mathbb{R}$). Finding the Domain and Range often involves identifying values for which the function is defined (e.g., avoiding division by zero or square roots of negative numbers). The Graph of a Real Function is the set of all points $(x, f(x))$ in the Cartesian plane, providing a visual representation of the relationship between input and output. We examine graphs of Standard Real Functions like the identity function ($f(x)=x$), modulus function ($f(x)=|x|$), polynomial functions, etc., and learn general techniques for Graphical Representation.
Operations on Functions
Functions can be combined using various operations. The Algebra of Functions defines pointwise operations: $(f+g)(x) = f(x)+g(x)$, $(f-g)(x) = f(x)-g(x)$, $(fg)(x) = f(x)g(x)$, and $(\frac{f}{g})(x) = \frac{f(x)}{g(x)}$ (where $g(x) \ne 0$). Composition of Functions is another operation where the output of one function becomes the input of another: $(f \circ g)(x) = f(g(x))$. The domain of the composite function depends on the domains of $f$ and $g$. Composition has properties like associativity but is generally not commutative.
Invertible Functions and Binary Operations
An Invertible Function $f: A \to B$ has an inverse function $f^{-1}: B \to A$ such that $(f^{-1} \circ f)(x) = x$ and $(f \circ f^{-1})(y) = y$. The essential Condition for a Function to be Invertible is that it must be Bijective (both one-to-one and onto). We learn the method for Finding the Inverse of a Function. A Binary Operation $*$ on a set S is a rule that assigns to each ordered pair of elements of S an element of S ($a*b \in S$). We examine Properties of Binary Operations such as Closure, Commutativity ($a*b = b*a$), Associativity ($(a*b)*c = a*(b*c)$), existence of an Identity element ($e*a = a*e = a$), and existence of an Inverse for each element.